Міністерство освіти і науки України Національний університет «Львівська політехніка» кафедра САПР
Лабораторна робота №2 з дисципліни: «Організація баз даних і знань» на тему: ПРЯМИЙ МЕТОД ДОСТУПУ ДО ФАЙЛІВНА ЗОВНІШНІХ ЗАПАМ’ЯТОВУЮЧИХ ПРИСТРОЯХ МЕТА РОБОТИ Розглянути органiзацiю i ведення файлiв прямого доступу; набути практичнi навички у програмуваннi алгоритмiв доступу хешуванням. 2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ МЕТОД ПРЯМОГО ДОСТУПУ Головною особливiстю прямого методу доступу є взаємна однозначна вiдповiднiсть мiж ключем запису i його фiзичною адресою. Фiзичне розмiщення запису визначається безпосередньо iз значення ключа. Створивши файл прямого доступу i видiливши для нього необхiдну дiлянку пам’ятi, можна вставляти записи у будь-якi мiсця файла. Перевага такого пiдходу над послiдовною органiзацiєю файла полягає у тому, що вдається отримати запис за заданим значенням ключа без попереднього перегляду всiх попереднiх записiв файла. ЕФЕКТИВНІСТЬ ДОСТУПУ дорiвнює одиницi. ЕФЕКТИВНІСТЬ ЗБЕРІГАННЯ залежить вiд густини ключiв. Якщо густина низька, пам’ять використовується неефективно, оскiльки резервуються адреси, що вiдповiдають вiдсутнiм ключам. У цьому випадку доцiльно використовувати для органiзацiї файла метод хешування. Пряму адресацiю можна важати частковим випадком методу хешування. ПОШУК Для того щоб за даним значенням ключа k знайти вiдповiдний запис, необхiдно визначити h(k) i потiм органiзувати лiнiйний пошук у блоцi, номер якого дорiвнює h(k). Цей пошук буде продовжуватися доти, поки не буде знайдений запис, значення первинного ключа якого збiгається iз заданим. ВСТАВЛЯННЯ Щоб вставити у файл новий запис, потрiбно за допомогою методу лiнiйного пошуку у блоцi, номер якого визначається значенням h(k), знайти вiльне мiсце. Пiсля цього на мiсце знайденого вiльного запису необхiдно розмiстити новий. Якщо при спробi помiстити новий запис у файл виявляється, що у знайденому блоцi немає вiльного мiсця, вважають, що блок переповнений. ВИДАЛЕННЯ Для видалення запису iз файла потрiбно, використовуючи метод лiнiйного пошуку, знайти запис у блоцi, номер якого дорiвнює h(k). Якщо запис буде знайдено то вiн видаляється, якщо нi, то очевидно, що блок був переповнений i необхiдно продовжити пошук. МОДИФІКАЦІЯ Якщо необхiдно модифiкувати запис, то потрiбно знайти цей запис i замiнити старi поля на новi. Нiяких iнших змiн не потрiбно. ПЕРЕПОВНЕННЯ Якщо необхiдно вставити новий запис, а у блоцi, призначеному для цього, немає мiсця, цей запис розмiщується у перший блок переповнення, в якому є вiльне мiсце. Пiсля цього необхiдно вставити цей запис у зв’язаний список записiв iз тим самим значенням функцiї хешування. ІНДИВІДУАЛЬНЕ ЗАВДАННЯ Написати програму методу зв'язаних записiв, яка реалiзує такi функцiї: 1. Друк бази даних. 2. Зчитування запису. 3. Введення запису. 4. Видалення запису. 5. Модифiкацiя запису. ТЕКСТ ПРОГРАМИ: Вміст файлу MAIN.CPP // include all the declarations #include "D:\lab2\DECL.CPP" // Global Variables char FileNameDB [FILENAME_LENGTH]; char IndexFile [FILENAME_LENGTH]; char BufferFileName [FILENAME_LENGTH]; int RecordSize = sizeof(struct Record) + NUMBER_OF_FIELDS_IN_RECORD * sizeof(char); // symbols ' ' long BlockSize = RecordSize * BLOCK_SIZE; void main (void) { clrscr(); printf("Insert filename of DataBase\n"); gets(FileNameDB); printf("\nInsert filename of Index file\n"); gets(IndexFile); getcwd(BufferFileName, FILENAME_LENGTH); strcat(BufferFileName, "\\buffer.txt"); // create files if they has not been created FILE * file = fopen(FileNameDB, "a+"); fclose(file); file = fopen(IndexFile, "a+"); fclose(file); // begin menu int answer; int Key = 1; Action action; while(Key) { // show the main menu printf("\n%d - Insert", Insert); printf("\n%d - Modify", Modify); printf("\n%d - Delete", Delete); printf("\n%d - Show fileBD", ShowDB); printf("\n%d - Find record", Find); printf("\n%d - Exit\n", Exit); scanf("%d", &answer); swit...